home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / readme.doc < prev    next >
Text File  |  1989-05-23  |  5KB  |  126 lines
  1. 11 April 1989
  2. Release Notes
  3.  
  4. Othello game-playing program, as described in
  5. The C Users Journal,
  6. Vol. 7, Number 3 (April 1989)
  7. pp. 89-96
  8.  
  9. Authors:
  10. Gary Culp, Jonathan Ward
  11. EmTech, Inc.
  12. 1418 Upfield, Suite 117
  13. Carrollton, TX  75006
  14.  
  15. =====================================================================
  16. Files:
  17.  
  18. L.BAT        batch file created because Jon is too lazy to type
  19. BDTTY.C      display routines
  20. BD_EVAL.C    board scoring
  21. BLDFA.C      separate utility that builds table in FATABL.C
  22. BUILDLVL.C   build the move tree a level deeper
  23. DUMPTREE.C   debugging functions
  24. FATABL.C     full-axis bits table (data)
  25. GETMOV.C     gets the human's move
  26. HEADER.C     junk
  27. MINIMAX.C    minimax search of move tree
  28. MOVEIT.C     verify & execute move (human's or computer's move)
  29. MOVE_GEN.C   move generator (finds 1 possible move)
  30. OTHDBM.C     database management routines
  31. OTHELLO.C    main
  32. PIECE_CT.C   count pieces of a given type / check each player's ability to move
  33. PROTECT.C    determines what pieces are permanent
  34. TESTDBM.C    dummy caller for testing database manager
  35. TESTDISP.C   dummy caller for testing display routines
  36. BLDFA.EXE    executable of BLDFA.C
  37. OTHELLO.EXE  executable game program
  38. OTHELLO.H    header file with #defines, prototypes, typedefs, etc.
  39. OTHELLO.LNK  linker response file for Microsoft LINK
  40. OTHELLO.MAK  makefile for Microsoft MAKE
  41.  
  42. =====================================================================
  43. Known bugs:
  44.  
  45. If the human player has just moved, and the game is now over, the
  46. computer may not immediately recognize that the game is over.
  47. Instead, it will say that it is unable to move and ask the player to
  48. press a key; THEN it will recognize that the game is over.
  49.  
  50. =====================================================================
  51. Enhancements:
  52. The rest of this document lists some of the improvements and
  53. variations we have considered for our Othello program, but not
  54. implemented.
  55.  
  56.  
  57. [] Pruning
  58.  
  59. The current version of the program considers every possible sequence
  60. of moves to a particular depth.  Alpha-beta pruning would reduce the
  61. number of boards that have to be scored, while still giving the same
  62. result.  The program would either be faster or could look ahead
  63. deeper (or both).
  64.  
  65. To implement alpha-beta pruning would require considerable changes to
  66. the database and tree-build sections of the program.
  67.  
  68.  
  69. [] Improvements to tree-build
  70.  
  71. The portion of the program that builds a level of the move tree is
  72. more complicated than it needs to be.  It should have been written as
  73. a recursive function.
  74.  
  75.  
  76. [] Different board scoring methods
  77.  
  78. Originally, the score for a board was based mostly on the number of
  79. permanent pieces of each color.  The number of non-permanent pieces
  80. of each color also had a small influence on the score.  
  81.  
  82. The current version of the program uses the same scoring scheme with
  83. a slight modification to discourage the computer from playing
  84. adjacent to an empty corner.  Playing adjacent to an empty corner is
  85. dangerous because, later in the game, it may provide the opponent a
  86. bridge to the corner.
  87.  
  88. Scoring boards according to the number of permanent pieces is a good
  89. technique for the middle of the game; but determining whether pieces
  90. are permanent is computationally expensive.  For the first few moves
  91. and the last few moves in the game, this effort is wastful.
  92.  
  93. In the early moves of the game, there are no permanent pieces, so
  94. there is no reason to look for them.  We can't make up our minds how
  95. boards should be scored in the early moves of the game.  The schemes
  96. we have considered involve assigning a weight to each square on the
  97. board which indicates how desirable it is to occupy that square.  One
  98. program we know of (written by Bart "Flatfingers" Stewart) tries to
  99. play in the 12 squares adjacent to the 4 central squares. (Remember,
  100. the 4 central squares are occupied at the beginning of the game.) The
  101. idea is to avoid playing adjacent to the outer edge, which would give
  102. the opponent a bridge to the outer edge.
  103.  
  104. In the last few moves of the game, it is practical to look ahead all
  105. the way to the end of the game, so just counting the number of pieces
  106. of each color is the most sensible way to score the boards
  107.  
  108.  
  109. [] Display routines
  110.  
  111. The display routines in the current version make very few assumptions
  112. about the display hardware.  A much prettier display, with graphics
  113. and colors, could be written.  Also, mouse support could be added to
  114. the program.
  115.  
  116.  
  117. [] .EXE size reduction
  118.  
  119. The limb_array in OTHDBM.C is allocated at compile time and make the
  120. .EXE file very big.  If limb_array were allocated at run time (with
  121. _fmalloc or some such function), the .EXE file would be a lot
  122. smaller.  The EXEPACK utility that comes with the Microsoft C
  123. compiler will also reduce the file size by about the same amount,
  124. with no changes to the source code.
  125.  
  126.